import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-08-05
 * Time: 21:27
 */
public class test1 {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        // 第一次遍历:创建新节点并建立映射
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        // 第二次遍历：设置next和random指针
        cur = head;
        while(cur!=null){
            // 判断有没有存在于map中
            Node clone = map.get(cur);
            clone.next = map.get(cur.next);
            clone.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


    class Node{
        int val;
        Node next;
        Node random;


        public Node(int val){
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


}
